package com.example.demo.offer;

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class Offer22 {
    public static void main(String[] args) {
        ListNode l5 = new ListNode(5);
        ListNode l4 = new ListNode(4,l5);
        ListNode l3 = new ListNode(3,l4);
        ListNode l2 = new ListNode(2,l3);
        l5.next = l3;
        ListNode head = new ListNode(1,l2);
        //System.out.println(detectCycle(head));
        System.out.println(detectCycleLenth(head));
    }

    public static ListNode detectCycle(ListNode head) {
        ListNode cur = head;
        Set<ListNode> set = new HashSet<>();
        while (cur != null ){
            if(set.contains(cur)){
                return cur;
            }else{
                set.add(cur);
            }
            cur = cur.next;
        }
        return null;
    }

    /**
     * 获取环的长度
     * @param head
     * @return
     */
    public static int detectCycleLenth(ListNode head) {
        //加入获取环的长度
        int length = 0;
        ListNode cur = head;
        Deque<ListNode> deque = new LinkedList();
        while (cur != null){
            if(deque.contains(cur)){
                for (int i = 0; i < deque.size(); i++) {
                    length++;
                    if(deque.poll() == cur){
                        return length;
                    }
                }
            }else{
                deque.offer(cur);
            }
            cur = cur.next;
        }
        return -1;
    }
}
